# -*- coding: utf-8 -*-
"""
    Time    : 2021/1/3 5:08 下午
    Author  : Thinkgamer
    File    : 015-三数之和.py
    Desc    : https://leetcode-cn.com/problems/3sum/
"""
"""
给你一个包含 n 个整数的数组nums，判断nums中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。
注意：答案中不可以包含重复的三元组。

示例：
给定数组 nums = [-1, 0, 1, 2, -1, -4]，

满足要求的三元组集合为：
[
  [-1, 0, 1],
  [-1, -1, 2]
]
"""


# 2356ms 5.02% | 18.3mb 5.09%
def three_sum(nums):
	if len(nums) < 3:
		return []
	# 创建一个字典，存放数组中出现的元素及个数
	num_count_dict = dict()
	for num in nums:
		num_count_dict.setdefault(num, 0)
		num_count_dict[num] += 1
	
	# 固定其中一个数 x ，看成是 两数求和问题, 因为要去重，所以 y 是在 x及之后的， z是在y及之后的
	result = list()
	keys = sorted(num_count_dict.keys())
	for x in range(len(keys)):
		num_count_dict[keys[x]] -= 1
		for y in range(x, len(keys)):
			if num_count_dict[keys[y]] > 0:
				z = 0 - keys[x] - keys[y]
				num_count_dict[keys[y]] -= 1
				if num_count_dict.get(z) and num_count_dict[z] > 0 and keys.index(z) >= y:
					result.append([keys[x], keys[y], z])
				num_count_dict[keys[y]] += 1
				num_count_dict[keys[x]] += 1
	
	return result


for nums in [
	[-1, 0, 1, 2, -1, -4],
	[-2, 0, 0, 2, 2],
	[0, 0, 0],
	[3, 0, -2, -1, 1, 2],
	[0],
	[0, -1, 1],
	[-1, -1, 0, 0, 1, 1],
	[-1, 0, 1, 2, -1, -4, -2, -3, 3, 0, 4],
]:
	result = three_sum(nums)
	print(result)
